package alorithm;

import org.junit.Test;
import util.GsonUtil;

/**
 * @Author Antony
 * @Since 2018/6/29 15:16
 */
public class PalindromicSubString {

    @Test
    public void test(){
        String str = "sfgkfkgfiuil";
        String s2 = "CCC";
//        System.out.println(GsonUtil.toJson(namacher(str)));
        System.out.println(GsonUtil.toJson(namacher(s2)));
    }

    private String namacher(String str){
        char[] t = preprocess(str);
        int[] p = new int[t.length];

        int mid=0, maxRight=0, length=0, center=0;
        for(int i=1; i<t.length-1; i++){
            int mirror = 2*mid - i;
            if(i < maxRight){
                if(p[mirror] < maxRight-i){
                    p[i] = p[mirror];
                    if(p[i] > length){
                        length = p[i];
                        center = i;
                    }
                    continue;
                }else{
                    p[i] = maxRight-i;
                }
            }
            while(t[i-p[i]-1] == t[i+p[i]+1]){
                p[i]++;
            }
            if(i + p[i] > maxRight){
                mid = i;
                maxRight = i+p[i];
            }

            if(p[i] > length){
                length = p[i];
                center = i;
            }
        }

        return str.substring((center-1-length)/2, (center-1+length)/2);
    }


    public String manacher_2(String str){
        char[] t = preprocess(str);
        int[] p = new int[t.length];

        int mid = 0, maxRight=0, length=0, center=0;
        for(int i=1; i<t.length-1; i++){
            int mirror = 2*mid -i;
            if(i < maxRight){
                p[i] = Math.min(maxRight-i, p[mirror]);
            }
            while(t[i+(1+p[i])] == t[i-(1+p[i])]){
                p[i]++;
            }
            if(i+p[i] > maxRight){
                mid = i;
                maxRight = i + p[i];
            }

            if(p[i] > length){
                length = p[i];
                center = i;
            }
        }
        return str.substring((center-1-length)/2, (center-1+length)/2);
    }

    private char[] preprocess(String str){
        char[] process = new char[str.length()*2 + 3];
        process[0] = '$';                   // 起始边界
        process[process.length - 1] = '@';  // 结束边界

        for(int i=0; i<str.length(); i++){
            process[i*2 + 1] = '#';
            process[i*2 + 2] = str.charAt(i);
        }
        process[process.length - 2] = '#';

        return process;
    }
}
